A. Field of the Invention
The present invention relates to a method and device for evaluating polynomials. In particular, the present invention relates to a method and device for speeding the evaluation of Galois field polynomials.
B. Description of the Related Art
Digital data transmission systems are used in a variety of different applications ranging from transferring financial numbers representing dollar amounts in bank accounts, to storing the music of our favorite performers on compact digital audio discs, to communicating telemetry data with aircraft and orbiting space satellites. To transmit this type of information, digital transmission systems deliver a sequence of binary information to a receiver across a transmission channel. Due to impairments in the transmission channel (i.e., the inability of the transmission channel to accurately deliver the transmitted bits), the binary information may become corrupted or changed as they traverse the transmission channel. If the errors remain undetected, the amounts in our bank accounts would be wrong, our favorite singers would be out of tune, and aircraft could be lost.
To prevent these problems, error detection schemes are employed to detect differences between the originally transmitted bits and the received data bits. When a transmission error is detected, the error detection scheme signals the transmitter to resend the corrupted information. More advanced error detection schemes, known as Forward-Error-Correction ("FEC"), can detect and correct corrupted information without requiring the transmitter re-send the information. FEC codes are essential in systems where the re-sending of information is not possible or practical. For example, in a compact audio disc there is not sufficient time to re-send the digital audio information without affecting the sound quality; with deep space probes re-sending the information may take a great deal of time.
A Galois finite field is a defined number system composed of a finite number of elements. A Galois finite field of q elements is usually denoted as GF(q). The q number of elements in a Galios field are of the form p.sup.M, where p is a prime integer and M is a positive integer.
Galois fields are particularly useful in FEC codes, such as Reed Solomon codes, for detecting and correcting errors in a transmitted sequence of binary information bits. For example, a sequence of binary information bits is first partitioned into a sequence of symbols, where each symbol is M-bits long. Each symbol is an element of a 2.sup.M element Galois field, denoted as GF(2.sup.M). The symbols are further partitioned into groups of K number of symbols represented by d.sub.K-1, d.sub.K-2, d.sub.K-3, . . . d.sub.2, d.sub.1, d.sub.0, where d.sub.K-1 is first in the sequence (transmitted first in time) and d.sub.0 last in the sequence (transmitted last). The sequence of transmitted symbols can thus be represented as an (K-1).sup.th order polynomial: EQU D(X)=d.sub.K-1 X.sup.K-1 +d.sub.K-2 X.sup.K-2 + . . . +d.sub.2 X.sup.2 +d.sub.1 X+d.sub.0
where X is a symbol delay operator and the d.sub.i 's are the coefficients of a Galois Field polynomial.
To implement a FEC using Galois field polynomials, redundant symbols are appended to the message stream. The resultant message is N symbols long and is called a codeword of the FEC. The methods for determining these redundant symbols are well known to those skilled in the art of error correction and described in "Error Control Coding: An Introduction," by Peter Sweeney, Prentice Hall 1991 and "Theory and Practice of Error Control Codes," by Richard E. Blahut, Addison-Wesley Publishing Company, Inc., 1983, which are hereby incorporated by reference. The transmitter transmits the modified message, which is received at the receiver, but is possibly corrupted. The receiver implements the FEC by treating the received symbols as coefficients of a Galois field polynomial. The polynomial is evaluated for certain input values where the evaluated results form a set called a syndrome, which holds the keys for locating errors in the message stream. The specifics of locating and correcting errors are well known to those skilled in the art and described in the above texts.
Calculating syndromes with Galois field polynomials may appear difficult, however, there are ways of simplifying polynomial equations so that the calculations can be more easily performed. One method of simplifying polynomial calculations, known as Horner's rule, states that a polynomial equation C(X)=c.sub.N-1 X.sup.N-1 +c.sub.N-2 X.sup.N-2 + . . . +c.sub.2 X.sup.2 +c.sub.1 X+c.sub.0 can be evaluated for a value of X=X.sub.i through a recursion which requires only addition and a sequential multiplication by the same value of X.sub.i. The polynomial C(X) can be factored or broken down into: EQU C(X.sub.i)=(. . . ((c.sub.N-1 X.sub.i +c.sub.N-2)X.sub.i +c.sub.N-3)X.sub.i + . . . +c.sub.1)X.sub.i +c.sub.0
As seen from the above recursive formula, the only multiplication required by the polynomial is multiplication by X.sub.i. In the recursive formula, c.sub.N-1 is multiplied by X.sub.i and c.sub.N-2 is added. The result of the addition is multiplied by X.sub.i again, and c.sub.N-3 is added. This operation simply repeats (N-1) times with each iteration having two steps: (1) the outcome of the previous step is multiplied by X.sub.i and (2) c.sub.k is added to the result. It will be appreciated by those skilled in the art that the addition and multiplication used to evaluate these polynomials do not follow the rules of ordinary addition and multiplication, but are Galois Field addition and multiplication.
Because evaluation of the polynomial equation requires only the multiplication by X.sub.i, a multiplication table L.sub.i can be created for a value of X.sub.i and stored by a programmable computer in memory. The multiplication lookup table L.sub.i is 2.sup.M elements long and contains the product of the input (index j) with X.sub.i : EQU L.sub.i (j)=j*X.sub.i.
In practice, for a small value of i, that is a small number of X.sub.i 's to evaluate the polynomial, a set of i multiplication tables are created and stored in computer memory. The polynomial evaluation process can then perform multiplication by indexing and retrieving the result in the proper lookup table stored in computer memory.
Horner's rule is highly sequential because each step is dependent on the outcome of the previous step, i.e., each iteration depends on the result of the previous iteration. Thus the polynomial equation must be evaluated serially, awaiting the outcome of the previous calculation. Accordingly, the rate at which the polynomial can be evaluated by a programmable computer is thus limited because each iteration must be evaluated in serial fashion. In computer processors having a long latency in performing memory accesses, this method of evaluating polynomials is inefficient. For example, a digital signal processor performs the multiplication by accessing the multiplication lookup table stored in memory. To return the result of a multiplication from memory, however, the processor may require a number of memory clock cycles. Meanwhile, the processor sits idle awaiting the result of the multiplication look-up table because each iteration of the polynomial calculation depends on the result of the previous iteration.